#include <stdio.h>
#include <malloc.h>
#define LIST_SIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType *elem;
    int length;
}SqList;
Status InitSqList(SqList &L)
{
    L.elem = (ElemType*)malloc(sizeof(ElemType) * LIST_SIZE);
    if (!L.elem)
        return OVERFLOW;
    L.length = 0;
    return OK;
}
typedef struct LNode
{
    ElemType data;
    struct LNode* next;

}LNode, *LinkList;
Status InitLinkList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (!L)
        return OVERFLOW;
    L->data = 0;
    L->next = NULL;
    return OK;
}
int main(void)
{
    // 线性表示 归并
    SqList sq1, sq2, sq3;
    InitSqList(sq1);
    InitSqList(sq2);
    InitSqList(sq3);
    for (int i = 1; i < 6; ++i)
    {
        sq1.elem[i-1] = i * i;
        sq2.elem[i-1] = 3 * i;
    }
    sq1.length = sq2.length = 5;
    int p1 = 0, p2 = 0;
    for (int i = 0; i < sq1.length + sq2.length; ++i)
    {
        if (p1 < sq1.length && p2 < sq2.length && sq1.elem[p1] > sq2.elem[p2])
            sq3.elem[i] = sq2.elem[p2++];
        else if (p1 < sq1.length && p2 < sq2.length && sq1.elem[p1] <= sq2.elem[p2])
            sq3.elem[i] = sq1.elem[p1++];
        else if (p1 >= sq1.length)
        {
            while (p2 < sq2.length)
                sq3.elem[i++] = sq2.elem[p2++];
            break;
        }
        else if (p2 >= sq2.length)
        {
            while (p1 < sq1.length)
                sq3.elem[i++] = sq1.elem[p1++];
            break;
        }
            
    }
    sq3.length = sq1.length + sq2.length;
    for (int i = 0; i < sq3.length; ++i)
        printf("%3d", sq3.elem[i]);
    printf("\n");
    // 链式表示 归并
    LinkList L1, L2, L3;
    InitLinkList(L1);
    LinkList lp1 = L1;
    for (int i = 0; i < 5; ++i)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = lp1->next;
        lp1->next = p;
        lp1 = lp1->next;
    }
    L1->data = 5;
    InitLinkList(L2);
    LinkList lp2 = L2;
    for (int i = 0; i < 7; ++i)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = lp2->next;
        lp2->next = p;
        lp2 = lp2->next;
    }
    L2->data = 7;
    InitLinkList(L3);
    lp1 = L1->next;
    lp2 = L2->next;
    LinkList lp3 = L3;
    while (lp1 && lp2)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        if (lp1->data > lp2->data)
        {
            p->data = lp2->data;
            lp2 = lp2->next;
        }
        else
        {
            p->data = lp1->data;
            lp1 = lp1->next;
        }
        p->next = lp3->next;
        lp3->next = p;
        lp3 = lp3->next;
    }
    if (lp1)
    {
        while (lp1)
        {
            LinkList p = (LinkList)malloc(sizeof(LNode));
            p->data = lp1->data;
            lp1 = lp1->next;
            p->next = lp3->next;
            lp3->next = p;
            lp3 = lp3->next;
        }
    }
    else if(lp2)
    {
        while (lp2)
        {
            LinkList p = (LinkList)malloc(sizeof(LNode));
            p->data = lp2->data;
            lp2 = lp2->next;
            p->next = lp3->next;
            lp3->next = p;
            lp3 = lp3->next;
        }
    }
    lp3 = L3->next;
    while (lp3)
    {
        printf("%3d", lp3->data);
        lp3 = lp3->next;
    }
    // input: 1 3 6 9 10 2 3 4 5 6 8 14
    return 0;  
}